/**
 * @param {string} s
 * @return {string}
 */
// dp[i][j]表示s[i, ... , j]是不是回文串
// 因此j >= i
var longestPalindrome = function (s) {
    let len = s.length
    if (len < 2) return true
    const dp = new Array(len).fill.map(() => {
        return new Array(len).fill(false)
    })
    for (let i = 0; i < len; i++) {
        dp[i][i] = true
    }
    let ans = 1
    for (let i = len - 1; i > 0; i--) {
        for (let j = i; j < len; j++) {
            if (s[i] !== s[j]) dp[i][j] = false
            else {
                if (j - i < 3) {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[ i + 1][j - 1]
                }
            }
            if(dp[i][j] && j - 1 + 1 > ans) ans = j - i + 1
        }
    }
    return ans
};